

#include<stdio.h>
#include<malloc.h>

struct Node {
     int val;
     struct Node *next;
     struct Node *random;
 };

struct Node* copyRandomList(struct Node* head) {
    struct Node * cur=head;
    if(!head)return head;
    while(cur)
    {
        struct Node *copy=(struct Node*)malloc(sizeof(struct Node));
        struct Node *next=cur->next;
        copy->val=cur->val;
        copy->next=next;
        cur->next=copy;
        cur=next;
    }
    cur=head;
    while(cur)
    {
        struct Node *copy=cur->next;
        struct Node *next=cur->next->next;
        if(cur->random==NULL)
            copy->random=NULL;
        else    
            copy->random=cur->random->next;
        cur=next;
    }
    cur=head;
    struct Node *head2=cur->next;
    while(cur)
    {
        struct Node *copy=cur->next;
        struct Node *next=cur->next->next;
        if(!next)
            copy->next=NULL;
        else copy->next=next->next;
        cur->next=next;
        cur=next;
    }
    

	return head2;
}